package com.sicheng.蓝桥.练习题.线段树.动态开点;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/25 20:55
 * <p>
 * 动态开点
 */
public class 我的日历 {
    static class Node {
        int ls, rs, add, max;
    }

    int N = (int) 1e9, M = 120010, cnt = 1;
    Node[] tr = new Node[M];

    void update(int st, int lc, int rc, int l, int r, int v) {
        lazyCreate(st);
        if (l == lc && rc == r) {
            tr[st].add += v;
            tr[st].max += v;
            return;
        }
        pushdown(st);
        int mid = lc + rc >> 1;
        if (r <= mid)
            update(tr[st].ls, lc, mid, l, r, v);
        else if (l > mid)
            update(tr[st].rs, mid + 1, rc, l, r, v);
        else {
            update(tr[st].ls, lc, mid, l, mid, v);
            update(tr[st].rs, mid + 1, rc, mid + 1, r, v);
        }
        pushup(st);
    }

    int query(int st, int lc, int rc, int l, int r) {
        lazyCreate(st);
        if (l == lc && rc == r)
            return tr[st].max;
        pushdown(st);
        int mid = lc + rc >> 1, ans = 0;
        if (r <= mid)
            ans = Math.max(ans, query(tr[st].ls, lc, mid, l, r));
        else if (l > mid)
            ans = Math.max(ans, query(tr[st].rs, mid + 1, rc, l, r));
        else {
            int max1 = query(tr[st].ls, lc, mid, l, mid);
            int max2 = query(tr[st].rs, mid + 1, rc, mid + 1, r);
            ans = Math.max(max1, max2);
        }
        return ans;
    }

    void lazyCreate(int st) {
        if (tr[st] == null)
            tr[st] = new Node();
        if (tr[st].ls == 0) {
            tr[st].ls = ++cnt;
            tr[tr[st].ls] = new Node();
        }
        if (tr[st].rs == 0) {
            tr[st].rs = ++cnt;
            tr[tr[st].rs] = new Node();
        }
    }

    void pushup(int st) {
        tr[st].max = Math.max(tr[tr[st].ls].max, tr[tr[st].rs].max);
    }

    void pushdown(int st) {
        if (tr[st].add > 0) {
            tr[tr[st].ls].add += tr[st].add;
            tr[tr[st].rs].add += tr[st].add;
            tr[tr[st].ls].max += tr[st].add;
            tr[tr[st].rs].max += tr[st].add;
            tr[st].add = 0;
        }

    }

    public boolean book(int start, int end) {
        if (query(1, 1, N + 1, start + 1, end) >= 2)
            return false;
        update(1, 1, N + 1, start + 1, end, 1);
        return true;
    }


//    链接：https://leetcode.cn/problems/my-calendar-ii/solution/by-ac_oier-okkc/

    public static void main(String[] args) {
        我的日历 solution = new 我的日历();
        System.out.println(solution.book(10, 20));
    }

}
